Combinatory logic and lambda-conversion were originally devised in the 1920s for investigating the foundations of mathematics using the basic concept of 'operation' instead of 'set'. They have now developed into linguistic tools, useful in several branches of logic and computer science, especially in the study of programming languages. These notes form a simple introduction to the two topics, suitable for a reader who has no previous knowledge of combinatory logic, but has taken an undergraduate course in predicate calculus and recursive (...) functions. The key ideas and basic results are presented, as well as a number of more specialised topics, and man), exercises are included to provide manipulative practice. (shrink)

Introduction Combinatory logic deals with a class of formal systems designed for studying certain primitive ways in which functions can be combined to form ...

Because the main difference between combinatory weak equality and λβ-equality is that the rule \begin{equation*}\tag{\xi} X = Y \vdash \lambda x.X = \lambda x.Y\end{equation*} is valid for the latter but not the former, it is easy to assume that another way of defining combinatory β-equality is to add rule (ξ) to the postulates for weak equality. However, to make this true, one must choose the definition of combinatory abstraction in (ξ) very carefully. If one tries to use one of the (...) more common abstraction algorithms, the result will be an equality, = ξ , that is either equivalent to βη-equality (and so strictly stronger than β-equality) or else strictly weaker than β-equality. This paper will study the relations = ξ for several commonly used abstraction algorithms, distinguish between them, and axiomatize them. (shrink)